/* 377. 组合总和 Ⅳ */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
/* 递归 */
var combinationSum4 = function (nums, target) {
    /* 
        key: target
        val:对于target 有几种组合
    */
    const map = new Map()
    const backtrack = (nums, target) => {
        if (target === 0) return 1
        if (map.has(target)) return map.get(target)
        let res = 0
        for (let i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                res += backtrack(nums, target - nums[i])
            }
        }

        map.set(target, res)
        return res
    }
    return backtrack(nums, target)
};
/* dp */
var combinationSum4 = function (nums, target) {
    const dp = new Array(target + 1).fill(0)
    dp[0] = 1
    for (let i = 1; i <= target; i++) {
        for (const num of nums) {
            if (num <= i) {
                dp[i] += dp[i - num]
            }
        }
    }
    return dp[target]
}
const ret = combinationSum4([9], 3)
console.log('combinationSum4 :>>', ret);